package codetop.microsoft.T76;

import java.util.HashMap;
import java.util.Map;

/**
 * @Author: 18362
 * @Create: 2022-08-14 14:15:17 星期日
 */
class Solution {
    public String minWindow(String s, String t) {
        int left = 0, right = 0, start = 0, minLen = Integer.MAX_VALUE, valid = 0;
        Map<Character, Integer> window = new HashMap<>(), need = new HashMap<>();
        for (int i=0; i<t.length(); ++i) {
            char c = t.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        while (right < s.length()) {
            char c = s.charAt(right++);
            if (need.containsKey(c)) {
                int origin = window.getOrDefault(c, 0);
                if (origin+1 == need.get(c)) {
                    valid++;
                }
                window.put(c, origin+1);
            }
            while (valid == need.size()) {
                if (right - left < minLen) {
                    minLen = right - left;
                    start = left;
                }
                char d = s.charAt(left++);
                if (need.containsKey(d)) {
                    int origin = window.get(d);
                    if (origin == need.get(d))
                        valid--;
                    window.put(d, origin-1);
                }
            }
        }
        return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start+minLen);
    }
}